The present invention relates, in general, to a method for fitting experimentally measured data to a form usable for a computer model, and more particularly to a method for piecewise linear curve fitting for cell characterization in integrated circuit design.
Integrated circuit design often involves large complex circuits having greater than 500,000 transistors. Such complex circuits are greatly simplified by use of techniques such as semicustom design where well understood and characterized building blocks called cells are arranged to obtain the circuit's required functionality. During the design process the propagation delay through any particular cell is predicted by means of a computer simulation. The same cells may be used in different locations throughout the design, may drive different loads, and may be driven by inputs having different speeds. In order to obtain an accurate simulation, the variation in propagation delay caused by each of these factors must be quickly and accurately predicted during the simulation. This may be accomplished in several ways, by actual experimentation with the physical circuit, a detailed analysis based on knowledge of the interior circuitry of the cell, and a detailed simulation using a low level circuit simulator such as the well known SPICE simulator. For example the propagation delay through the cell may be simulated using different values of load capacitance and measuring the simulated delay. The points obtained are then plotted and a curve is drawn through these points according to the user's requirements.
There are numerous methods for using this information to create a computer model which can rapidly and accurately interpolate between these observations. One commonly used method is called a piecewise linear model which approximates the actual variation of the data by a series of straight lines. A piecewise linear model is simple, computes rapidly, and requires minimal computer memory. As a result such a model is widely used for simulating phenomena where no closed form equation is known or where the known equation is complex.
The accuracy of a piecewise linear model is related not only to the number of line segments used, but to the careful selection of the breakpoints where one line ends and another begins. Typically fewer than five segments may model a behavior which is characterized by several hundred observations. The most accurate model would simply be for each observation to become a breakpoint. This is impractical since the computer memory required would be excessive. In addition, the computation required to select the two closest observations for interpolation becomes excessive with large numbers of breakpoints. The prior art includes numerous methods for determining optimal breakpoints, however these are not suited to automatic computation by a computer. According to the prior art, breakpoints are typically determined by estimating the required number of segments, selecting breakpoints, then manually computing the error which occurs at each observed point. The prior art method is tedious and error prone with no guarantee that optimal accuracy will be achieved.
A typical cell library may contain more than 100 cells, each cell having 5 or more parameters to model with each parameter being characterized by more than 100 observation points. Accordingly, there is a need for a solution which computes the breakpoints and selects the numbers of segments which will satisfy a user defined error tolerance. Alternatively derivation of the optimal model for a limited number of segments is required. The solution must be completely automatic and suitable for computer calculation. A useful method must also be suitable for integration into the basic model of a computer simulation system such that the characterization results may be used to provide accurate prediction of results which will be obtained when using the cells in actual designs.